//
// Created by Administrator on 2021/4/14.
//
/*
给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。


示例 ：

输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

5
/ \
    3    6
/ \    \
  2   4    8
/        / \
1        7   9

输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7
             \
              8
               \
                 9

提示：

给定树中的结点数介于 1 和100 之间。
每个结点都有一个从 0 到 1000 范围内的唯一整数值。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/increasing-order-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/



#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;


struct TreeNode {
    int val; // 节点值
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

class Solution {
private:
    vector<TreeNode *> v;

public:
    TreeNode *increasingBST(TreeNode *root) {
        dfs(root);
        v.push_back(nullptr);
        for (int i = 0; i < v.size()-1; ++i) {
            v[i]->left = nullptr;
            v[i]->right = v[i + 1];
        }
        return v.front();
    }

    void dfs(TreeNode *root) {
        if (!root) return;
        dfs(root->left);
        v.push_back(root);
        dfs(root->right);
    }
};
class Solution2 {
public:
    TreeNode* increasingBST(TreeNode* root, TreeNode* tail = nullptr) {
        if (!root) return tail;
        auto head = increasingBST(root->left, root);
        root->left = nullptr;
        root->right = increasingBST(root->right, tail);
        return head;
    }
};


int main() {
    auto t9 = TreeNode(9);
    auto t8 = TreeNode(7);
    auto t7 = TreeNode(1);
    auto t6 = TreeNode(8, &t8, &t9);
    auto t5 = TreeNode(4);
    auto t4 = TreeNode(2, &t7, nullptr);
    auto t3 = TreeNode(6, nullptr, &t6);
    auto t2 = TreeNode(3, &t4, &t5);
    auto t1 = TreeNode(5, &t2, &t3);

    Solution2 sol;
    sol.increasingBST(&t1);
    return 0;
}